package com.datastructure.test.candivide;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class CanDivide {

    public boolean candivide (ArrayList<Integer> nums, int k) {
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        if (sum % k != 0) return false;
        sum /= k;
        Collections.sort(nums);
        if (nums.get(nums.size()-1) > sum) return false;
        int[] bucket = new int[k];
        Arrays.fill(bucket, sum);
        return back(nums, bucket, nums.size()-1);
    }
    public boolean back(ArrayList<Integer> nums, int[] bucket, int idx) {
        if (idx < 0) return true;
        for (int i = 0; i < bucket.length; i++) {
            if (bucket[i] == nums.get(idx) || (bucket[i] - nums.get(idx) >= nums.get(0))) {
                bucket[i] -= nums.get(idx);
                if (back(nums, bucket, idx-1)) return true;
                bucket[i] += nums.get(idx);
            }
        }
        return false;
    }
}
